package com.neusoft.sort.radix;

import org.apache.commons.lang.StringUtils;

/**
 * @Author lichunlong lcl253137@alibaba-inc.com
 * @Desc 基数排序
 * @Date 2024-11-19
 */
public class RadixSort {

    public static void radixSort(int[] arr) {
        int arrMaxDigit = getMaxDigitLength(arr);
        // 二维数组表示10个桶, ，分别表示0-9的桶下标。每个桶就是一个一维数组
        int[][] bucket = new int[10][arr.length];
        // 记录每个桶中，实际存放了多少个数据, 定义一个一维数组来记录各个桶的每次放入的数据个数
        int[] bucketElementCounts = new int[10];
        // 遍历数组的位数: 个位、十位、百位、千位...
        for (int i = 0, x = 1; i < arrMaxDigit; i++, x = x * 10) {
            // 遍历数组中的数据, 放入到对应的桶中
            for (int value : arr) {
                //取出每个元素的对应位的值
                int digitOfElement = (value / x) % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = value;
                bucketElementCounts[digitOfElement]++;
            }

            // 遍历每个桶中的数据，放入到原数组
            int index = 0;
            // 遍历每一个桶
            for (int j = 0; j < bucket.length; j++) {
                // 遍历每个桶中的数据
                for (int k = 0; k < bucketElementCounts[j]; k++) {
                    arr[index] = bucket[j][k];
                    // 重置二维数组中数据
                    bucket[j][k] = 0;
                    index++;
                }
                // 重置每个桶中的计数器
                bucketElementCounts[j] = 0;
            }
        }
    }

    /**
     * 获取数组中最大数的位数
     *
     * @param arr 待排序数组
     * @return 最大数的位数
     */
    private static int getMaxDigitLength(int[] arr) {
        // 假设第一数就是最大数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        return (max + StringUtils.EMPTY).length();
    }
}
